with(combinat):
helpYPP:=proc()
 print(`redu(), classifier(pi, l)`);
end:
#inputs a list of numbers, and outputs the reduction as a permutation of nops(L)
#redu([e,pi,gamma,phi, h])=[ 4, 5 , 2 , 3    ,1]
redu:=proc(L) local L1,T,k,i:
L1:=sort(sort(L,'output'='permutation'),'output'='permutation'):

end:

#classifier(pi,l) takes a permutation pi and a prefix length l and outputs a list with two elements. The first element is a copy of the portion of the original permutation following the prefix, but each element is replaced with the number of prefix elements that it exceeds, plus one. The second element is a list with two more elements than the number of elements in the prefix. The ith element is the reduction of the subpermutation formed by only considering the elements of the original permutation greater than exactly (i-1) permutation elements, and the last element is the reduction of the prefix.


classifier:=proc(pi, l) local n,i,el1, el2,j,k:
n:=nops(pi):
el1:=[]:
el2:=[[]$(l+2)]:
for i from l+1 to n do
 j:=0:
 for k from 1 to l do
  if pi[k]<pi[i] then
   j:=j+1:
  fi:
 od:
 el1:=[op(el1),j+1]:
 el2[j+1]:=[op(el2[j+1]),pi[i]]:
od:
for i from 1 to l+1 do
 el2[i]:=redu(el2[i]):
od:
el2[l+2]:=redu([op(1..l,pi)]):
return([el1,el2]):
end:

#cross_prod(n,d) inputs integers n and d and outputs [n]^d
cross_prod:=proc(n,d) local output, prev, i, j:
output:={[]}:
for i from 1 to d do
 for prev in output do
  for j from 1 to n do
   output:=output union {[op(prev),j]}:
  od:
  output:= output minus {prev}:
 od:
od:

output:
end: 

#gen_indices(n,k) generates all k-subsets of n
gen_indices:=proc(n,k) local output, i, j, p, prev:
option remember:
if k=1 then
 RETURN({seq({i},i=1..n)}):
fi:

prev:=gen_indices(n,k-1):
output:={}:

for p in prev do
 for i in {seq(j,j=1..n)} minus p do
  output:=output union {p union {i}}:
 od:
od:

output:
end:

#test_subword1(subword, word) considers a subword and set of words and returns true if it contains subword as a subword
test_subword1:=proc(subword, word) local m,n,indices, index, check,i:
n:=nops(word):
m:=nops(subword):
indices:=gen_indices(n,m):
for index in indices do
 check:=[]:
 for i from 1 to nops(index) do
  check:=[op(check),word[index[i]]]:
 od:
 if check=subword then
  RETURN(true):
 fi:
od:
RETURN(false):
end:




#all_test_subword(subwords, words) considers a set of subwords and set of words and returns true if they all contain a subword in subwords and false otherwise
all_test_subword:=proc(subwords, words) local word, found, subword:
for word in words do
 found:=false:
 for subword in subwords do
  if test_subword1(subword, word)=true then
   found:=true:
  fi:
 od:
 if found=false then
  RETURN(false):
 fi:
od:
RETURN(true):
end:

#any_test_subword(subword, words considers a subword and set of words and returns true if any of them contain subword as a subword and false otherwise

any_test_subword:=proc(subword, words) local word:
for word in words do
 if test_subword1(subword, word) = true then
  RETURN(true):
 fi:
od:
RETURN(false):
end: